home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / intrvews / xgrab.lha / xgrab / include / digraph.h < prev    next >
Encoding:
C/C++ Source or Header  |  1990-03-06  |  11.9 KB  |  335 lines
  1. /**
  2.    GRAB Graph Layout and Browser System
  3.  
  4.    Copyright (c) 1986, 1988 Regents of the University of California
  5.    Copyright (c) 1989, Tera Computer Company
  6.  **/
  7.  
  8.   /* digraph.h -- definitions for a DIGRAPH */
  9.  
  10. #ifndef digraph_h
  11. #define digraph_h
  12.  
  13. #include <stdio.h>
  14. #include "attribute.h"
  15. #include "set.h"
  16.  
  17. #define    new(p, t)    {p = (t *) malloc(sizeof(t));}
  18.    /* Mimic Pascal new function */
  19.  
  20. #define    dispose(p)    free((char *) p)
  21.  
  22. #define    MAXNODES    2000    /* maximum number of nodes */
  23. #define    MAXHASH        511     /* vertex hash table size (it isn't prime) */
  24.  
  25. #define    NO_BC        -1.0    /* indicates no barycenter */
  26.  
  27. typedef enum {UP, DOWN, UPDOWN} DIRECTION;    /* for bc's and priorities */
  28. #define NUM_DIRECTION 3
  29.  
  30. #define MAX(A,B)    ( (A) > (B) ? (A) : (B) )
  31. #define MIN(A,B)    ( (A) < (B) ? (A) : (B) )
  32.  
  33. typedef int VNO;        /* vertex number */
  34. typedef int LNO;        /* level number */
  35.  
  36. typedef struct outedge OUTEDGE;
  37.  
  38. struct outedge
  39. {
  40.    VNO to_vno;          /* vertex at the head of the edge */
  41.    BOOL edge_reversed;    /* has this edge been reversed? */
  42.    BRUSH brush;        /* how to draw it */
  43.    COLOR color;        /* color to draw it */
  44.    char **attributes;    /* user-defined attributes for the edge */
  45.    int ordinality;    /* for multigraphs; determines whether this is the 
  46.                first, second, etc. edge from a to b.  Useful
  47.                for identification and layout heuristics */
  48.    OUTEDGE *next;          /* next edge */
  49. };
  50.  
  51. typedef struct inedge INEDGE;
  52.  
  53. struct inedge
  54. {
  55.    VNO from_vno;          /* vertex at the head of the edge */
  56.    BOOL edge_reversed;    /* has this edge been reversed? */
  57.    int ordinality;    /* for multigraphs; determines whether this is the 
  58.                first, second, etc. edge from a to b.  Useful
  59.                for identification and layout heuristics */
  60.    INEDGE *next;          /* next inedge */
  61. };
  62.  
  63. typedef struct vertex VERTEX;
  64.  
  65. struct vertex
  66. {
  67.    char *name;      /* name of the vertex */
  68.    VNO vno;         /* vertex number */
  69.    VERTEX *next;    /* next in chain */
  70. };
  71.    
  72. typedef float BC;                /* barycenter */
  73.  
  74. typedef struct node MEMBER;
  75.  
  76. struct node
  77. {
  78.    VERTEX *vertex;  /* vertex info */
  79.    VNO coalescer_vno; /* vno of the container of this node */
  80.    OUTEDGE *out_edges; /* outgoing edges */
  81.    INEDGE *in_edges;   /* incoming edges */
  82.    SET *succ_set;   /* succedent set of vertices */
  83.    SET *ante_set;   /* antecedent set of vertices */
  84.      /**
  85.     there is a distinction between the antecedents/succedents and the 
  86.     in_edges/out_edges of a node.  It's best thought of in this way:
  87.     in_edges/out_edges represent the abstract (undrawn) graph.  
  88.     Antecedents/succedents represent the layed out graph.  Hence,
  89.     coalescer nodes and dummy nodes have no in or out edges, because
  90.     they aren't part of the abstract graph, only the displayed (layed
  91.     out) graph.
  92.  
  93.     Also, because the successor and antecedent sets are *sets*, they
  94.     only indicate links between two nodes.  Multiple edges are possible,
  95.     but you can't tell if there are multiple edges without looking at 
  96.     the inedge/outedge lists.
  97.  
  98.     These distinction is very important when drawing the graph.  Generally,
  99.     routines should only access the successor and ancestor sets directly,
  100.     using the routines in util.c to access the in and out edges.
  101.  
  102.     Finally, just to make things more confusing, note that edges can
  103.     be reversed, and ante and succ sets get reversed along with the edges.
  104.     So, for example, to check for the parents of a node, you must consider
  105.     at both the ancestor and successor sets (or the in and out edge lists).
  106.       **/
  107.    int x_position;  /* x position of center of node */
  108.    int y_position;  /* y position of center of node */
  109.    int half_width;  /* half of width */
  110.    int half_height; /* half of height */
  111.    SHAPE shape;     /* shape of node */
  112.    BRUSH brush;        /* how to draw it */
  113.    COLOR color;        /* color to draw it */
  114.    char **attributes;  /* user-defined attributes for the node */
  115.    BOOL coalesced;  /* if true, the node is contained in another node.  
  116.      /**
  117.     Note: if coalesced is true, displayed had better be false 
  118.  
  119.     coalesced nodes should have the proper ante/succ sets, indicating
  120.     their (displayed) neighbors.  This facilitates expanding a node.
  121.     fix_ante_succ_sets, in relay.c, properly builds the ante_succ sets
  122.     given the outedge lists.
  123.  
  124.     currently, no coalesced nodes are found in ante/succ sets.  Instead,
  125.     the topmost coalescer of the node is given.  This makes expansion
  126.     somewhat difficult if the coalescer node has coalescer neighbors 
  127.     (because you have to find out which element of the coalescer was
  128.     the original neighbor of the coalescer).  The alternative is to 
  129.     keep only non-coalescer nodes in ante/succ sets, and chase down the
  130.     chain of coalescer_vno's every time.  I expect that chasing down
  131.     the chain would be done often, wheras coalesces and expands are done
  132.     less often, so the current implementation is probably more efficient.
  133.       **/
  134.    BOOL coalescer;  /* if true, the node contains other nodes */
  135.    SET *expansion;  /* members of a coalescer node */
  136.    BOOL displayed;  /* if false, the node is there, but it isn't drawn or
  137.                considered when laying out the graph */
  138.      /* the following fields are considered to be member fields */
  139.    int level_no;    /* level number of node */
  140.    int position;    /* position on level */
  141.    STATUS status;   /* node type:  NORMAL or DUMMY */
  142.    int last_dummy;  /* e.g. ->name.1, last dummy number used */
  143.    BC bc[NUM_DIRECTION - 1];  /* up and down barycenters (no updown) */
  144.    BOOL is_layed;   /* TRUE if this member is layed out */
  145.    int priority[NUM_DIRECTION]; /* up, down, and updown priorities */
  146.    MEMBER *prev;    /* previous vertex on the level */
  147.    MEMBER *next;    /* next vertex on the level */
  148. };
  149.  
  150. typedef struct node NODE;
  151.  
  152. typedef struct level LEVEL;
  153.  
  154. struct level
  155. {
  156.    LNO lno;         /* level number */
  157.    SET *members;    /* members of this level */
  158.    MEMBER *order;   /* order of the members */
  159.    int offset;      /* offset from previous level */
  160.    int num_cross;   /* number of crossings for this level and next */
  161.    LEVEL *prev;     /* previous level */
  162.    LEVEL *next;     /* next level */
  163. };
  164.  
  165. struct digraph
  166. {
  167.    VERTEX *hashtbl[MAXHASH];   /* hash table of vertex names */
  168.    int lastnode;               /* last node in nodes */
  169.    NODE *nodes[MAXNODES];      /* nodes in the graph */
  170.    LEVEL *levels;              /* the digraph levels */
  171.    LEVEL *lastlevel;           /* the last level */
  172.    char *title;               /* name of digraph */
  173.    int num_node_attributes;    /* number of user-defined attributes per node */
  174.    int num_edge_attributes;    /* number of user-defined attributes per edge */
  175.    int dist_edge_attribute;    /* index of the edge attribute to use as a 
  176.                    label (currently, it's always 0) */
  177.    int dist_node_attribute;    /* index of the node attribute to use as a 
  178.                    label (currently, it's always 0) */
  179.    char **node_att_names;      /* names of the user-defined node attributes */
  180.    char **edge_att_names;      /* names of the user-defined edge attributes */
  181. };
  182.  
  183. typedef struct digraph DIGRAPH;
  184.  
  185. #define    strsave(p, s)    \
  186. {\
  187.     p = (char *) malloc(strlen(s) + 1);    \
  188.     strcpy(p, s);    \
  189. }
  190.  
  191. #define    loop            /* nothing */
  192. #define    endloop            }}
  193.  
  194. #define    Node_member(node)    ((MEMBER *) node)
  195. #define    Member_node(member)    ((NODE *) member)
  196.  
  197. #define    Node(digraph, vno)    digraph->nodes[vno]
  198. #define    Member(digraph, vno)    Node_member(Node(digraph, vno))
  199.  
  200.   /* loop through all the *displayed* nodes */
  201. #define    each_node(digraph, node)    \
  202.    {\
  203.       VNO _vno;\
  204.       for (_vno = 0; _vno <= digraph->lastnode; _vno++)\
  205.       {\
  206.       node = Node(digraph, _vno); \
  207.      if (node == NULL || !Displayed(node)) \
  208.          continue;
  209.  
  210.   /* loop through every node */
  211. #define all_nodes(digraph, node)    \
  212.    {\
  213.       VNO _vno;\
  214.       for (_vno = 0; _vno <= digraph->lastnode; _vno++)\
  215.       {\
  216.       node = Node(digraph, _vno); \
  217.      if (node == NULL) \
  218.          continue;
  219.  
  220.   /**
  221.      note that there is no equivalent to each_node for in and out edges,
  222.      because that would imply we're looking at in or out edges (the
  223.      abstract graph) and worried about whether a node is displayed or not
  224.      (the layed out graph).  A desire for such a construct indicates muddy
  225.      thinking.
  226.    **/
  227. #define    all_out_edges(node, edge)    \
  228.    {\
  229.       OUTEDGE *_next_edge;\
  230.       for (edge = node->out_edges; edge != NULL; edge = _next_edge)\
  231.       {\
  232.      _next_edge = edge->next;
  233.  
  234. #define    all_in_edges(node, edge)    \
  235.    {\
  236.       INEDGE *_next_edge;\
  237.       for (edge = node->in_edges; edge != NULL; edge = _next_edge)\
  238.       {\
  239.      _next_edge = edge->next;
  240.  
  241. #define Title(digraph)        (digraph)->title
  242. #define First_level(digraph)    (digraph)->levels
  243. #define    Last_level(digraph)    (digraph)->lastlevel
  244. #define DNodeAttr(digraph)    (digraph)->dist_node_attribute
  245. #define DEdgeAttr(digraph)    (digraph)->dist_edge_attribute
  246. #define NNodeAttr(digraph)    (digraph)->num_node_attributes
  247. #define NEdgeAttr(digraph)    (digraph)->num_edge_attributes
  248. #define NAttrName(digraph, num) (digraph)->node_att_names[num]
  249. #define EAttrName(digraph, num) (digraph)->edge_att_names[num]
  250.  
  251. #define    To_vno(edge)        (edge)->to_vno
  252. #define    From_vno(edge)        (edge)->from_vno
  253. #define    Label(edge)    (edge)->attributes[(digraph)->dist_edge_attribute]
  254. #define EAttr(edge, num)    (edge)->attributes[num]
  255. #define Edge_reversed(edge)    (edge)->edge_reversed
  256. #define Ord(edge)        (edge)->ordinality
  257.  
  258. #define Coalesced(node)        (node)->coalesced
  259. #define Coalescer(node)        (node)->coalescer
  260. #define Expansion(node)        (node)->expansion
  261. #define    Coalescer_vno(node)    (node)->coalescer_vno
  262. #define Displayed(node)        (node)->displayed
  263. #define    Vno(node)        (node)->vertex->vno
  264. #define    Name(node)        (node)->vertex->name
  265. #define    Text(node)    (node)->attributes[(digraph)->dist_node_attribute]
  266. #define NAttr(node, num)    (node)->attributes[num]
  267. #define    Succ_set(node)        (node)->succ_set
  268. #define    Ante_set(node)        (node)->ante_set
  269.  
  270. #define    Lno(level)        (level)->lno
  271. #define    Num_cross(level)    (level)->num_cross
  272. #define    Members(level)        (level)->members
  273. #define    Order(level)        (level)->order
  274. #define    Offset(level)        (level)->offset
  275. #define    Prev_level(level)    (level)->prev
  276. #define    Next_level(level)    (level)->next
  277.  
  278. #define    X_position(member)    (member)->x_position
  279. #define    Y_position(member)    (member)->y_position
  280. #define    Half_width(member)    (member)->half_width
  281. #define    Half_height(member)    (member)->half_height
  282. #define    Shape(member)        (member)->shape
  283. #define    Brush(member)        (member)->brush
  284. #define    Color(member)        (member)->color
  285. #define    Level_no(member)    (member)->level_no
  286. #define    Position(member)    (member)->position
  287. #define    Status(member)        (member)->status
  288. #define    Last_dummy(member)    (member)->last_dummy
  289. #define    Is_dummy(member)    (Status(member) == DUMMY)
  290. #define    Is_layed(member)    (member)->is_layed
  291. #define    X_left(member)        (X_position(member) - Half_width(member))
  292. #define    X_right(member)        (X_position(member) + Half_width(member))
  293. #define    Y_bottom(member)    (Y_position(member) - Half_height(member))
  294. #define    Y_top(member)        (Y_position(member) + Half_height(member))
  295. #define    Bc(member, direction)    (member)->bc[(int) direction]
  296. #define    Has_bc(member, direction)  (Bc((member), (int) direction) != NO_BC)
  297. #define    Priority(member, direction)  (member)->priority[(int) direction]
  298. #define    Prev_member(member)    (member)->prev
  299. #define    Next_member(member)    (member)->next
  300.  
  301.  
  302. #define    each_level(digraph, level)    \
  303.    {\
  304.       LEVEL * _next_level;\
  305.       for (level = digraph->levels; level != NULL; level = _next_level)\
  306.       {\
  307.      _next_level = Next_level(level);
  308.  
  309. #define    each_level_reverse(digraph, level)    \
  310.    {\
  311.       LEVEL * _prev_level;\
  312.       for (level = digraph->lastlevel; level != NULL; level = _prev_level)\
  313.       {\
  314.      _prev_level = Prev_level(level);
  315.  
  316. #define    each_member(level, member)    \
  317.    {\
  318.       for (member = Order(level); member != NULL; member = member->next)\
  319.       {
  320.  
  321.  
  322. #define HALF_CHAR         50
  323. #define GAP            5 * HALF_CHAR    /* space between nodes */
  324. #define NODE_HALF_HEIGHT    5 * HALF_CHAR
  325. #define Node_half_width(node)    HALF_CHAR * (strlen(Text(node)) + 1)
  326. #define DUMMY_HALF_WIDTH    2 * HALF_CHAR
  327. #define NULL_STRING         "\0"
  328. #define EDGE_GAP        HALF_CHAR
  329.               /* space between multiple edges into/out of a node */
  330.  
  331. extern DIGRAPH *digraph;
  332. extern BOOL straightenEdges;
  333.  
  334. #endif
  335.